Exact Thinking in Demented Times by Karl Sigmund

Author:Karl Sigmund
Language: eng
Format: epub
Publisher: Basic Books
Published: 2017-12-05T05:00:00+00:00

GÖDEL NUMBERING

Gödel’s proof occupies dozens of pages, yet it is based on a stunningly simple basic idea. In any formal system, mathematical statements are simply strings of symbols. Gödel found a systematic way of turning any such string into a unique integer (always a huge integer, as it happens, but that detail didn’t affect anything). The given string of symbols determined its integer uniquely (that is, the string could be mechanically “encoded” as an integer), and vice versa—given a large integer, if it represented a string of symbols, then that string was uniquely determined (the large integer could be mechanically “decoded,” if you will). These large integers were later called the Gödel numbers of their associated strings, and the encoding/decoding recipe was called Gödel numbering.

The next idea came from the fact that proofs in Principia Mathematica (or any other formal system) were built up regularly, in a way that could be mirrored in the world of numbers. Thus for any theorem there was a theorem-number that could be defined in terms of addition, multiplication, and other mathematical concepts. Therefore, provability of a string in a formal system corresponded to a purely mathematical property of a very large number, and this property could be talked about using the notation of Principia Mathematica. In other words, just as one can assert of a number N that it is a square or a cube or a prime number, and prove all sorts of theorems about such notions (e.g., “There are infinitely many primes”), so one can assert of N that it is a theorem-number, and there are all sorts of theorems about this more complex notion of “theorem-numberhood” (e.g., “There are infinitely many theorem-numbers”). And in this way, Principia Mathematica acquired the ability to talk (in code) about the provability or the nonprovability of strings in Principia Mathematica itself. Talk about a snake biting its own tail!

Gödel’s coup de grâce was the construction of a special mathematical proposition G that asserted that a certain string having Gödel number g is unprovable—meaning that it cannot be formally derived from the system of axioms of Principia Mathematica. And astonishingly, Gödel managed to arrange things so that the integer g was precisely the Gödel number of the statement G (“somewhat fortuitously,” as he slyly noted).

Proposition G thus asserts its own nontheoremhood, or unprovability, inside Principia Mathematica. You might paraphrase G as saying “I am unprovable inside Principia Mathematica.” Now is G true, or is it false? Is it provable, or is it unprovable? Well, if G is actually proven, this leads to a contradiction; and conversely, if its negation, not-G, is proven, this leads to another contradiction. This sounds like a disaster, leading inevitably to a self-contradictory system—but wait! Perhaps neither G nor not-G is provable. In that case, the system (Principia Mathematica) is saved from being self-contradictory, but only at the price of being forever unable to decide which of G and not-G it “believes.”

In short, if Principia Mathematica is consistent, meaning that it will

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.